package 算法.leetcode.labuladong.二叉树;

import 算法.leetcode.offer.base.TreeNode;

/**
 * @author lchenglong
 * @date 2022/6/24
 */
public class 在二叉树中分硬币 {
    class Solution {
        // 如果一个节点的硬币个数是 x，无论是移出还是移入，
        // 把该节点的硬币个数变成 1 的最少移动次数必然是 abs(x - 1)
        int ans=0;
        public int distributeCoins(TreeNode root) {
            dfs(root);
            return ans;
        }

        public int dfs(TreeNode root){
            // base case
            if (root == null)return 0;
            // 左子树
            int left = dfs(root.left);
            // 右子树
            int right = dfs(root.right);
            ans += Math.abs(left) +Math.abs(right) + (root.val -1);
            // 函数的定义: 移动最小次数 = (左子树移动最小次数)+(右子树移动最小次数)+(当前节点移动最小次数)
            // 当前节点移动最小次数 =  abs(x-1)
            return left + right + (root.val - 1);
        }
    }
}
